// 给定一个链表，判断链表中是否有环。
// 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
// 如果链表中存在环，则返回 true 。 否则，返回 false。

// 要求：空间复杂度为O1

function hasCycle(head: ListNode | null): boolean {
    let fast: ListNode | null = head;// 快指针
    let slow: ListNode | null = head;// 慢指针
    do {
        if (fast === null || fast.next === null) return false;// 快指针走到终点，返回false
        fast = fast.next.next;
        slow = slow!.next;
    } while (fast !== slow)
    return true;// 当fast与slow相遇时说明有环
};


// 这道题是一道非常经典的例题
// 一般看到链表的环状问题，基本都可以判断出来是使用快慢指针来解决
// 快指针每次走两步，慢指针每次走一步
// 当快指针本身或下一位置走到空节点时，说明这是一个线性表，返回false
// 而当快慢指针相遇的时候，说明链表中有环
// 根据上述的原理写出代码即可。
